package club.xiaojiawei.dp;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/8/22 11:13 PM
 * @question 583. 两个字符串的删除操作
 * @description 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
 * 每步 可以删除任意一个字符串中的一个字符。
 */
public class MinDistance583 {

    public static void main(String[] args) {
        MinDistance583 test = new MinDistance583();
        int result = test.minDistance("leetcode", "etco");
        System.out.println(result);
    }

    /**
     * dp-二维数组
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
//        dp[i][j] = k 表示word1从开头到下标为i，word2从开头到下标为j的时候最长公共子序列为k
        int[][] dp = new int[length1 + 1][length2 + 1];
        for (int i = 1; i <= length1; i++) {
            char target = word1.charAt(i - 1);
            for (int j = 1; j <= length2; j++) {
                if (target == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return length1 + length2 - (dp[length1][length2] << 1);
    }

    /**
     * 民间- dp（滚动数组）
     * 数据量相同的情况下，二维数组比一维数组需要开辟更大的内存空间
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance2(String word1, String word2){
        char[] w1Array = word1.toCharArray();
        char[] w2Array = word2.toCharArray();
        int n1 = w2Array.length;
        int n2 = w1Array.length;
        int[] dp =new int[n2 + 1];
        for(int j = 1; j <= n2; j++){
            dp[j] = j;
        }
        for(int i = 1; i <= n1; i++){
            dp[0] = i;
            int stor, use = i - 1;
            for(int j = 1; j <= n2; j++){
                stor = dp[j];
                if(w2Array[i - 1] == w1Array[j - 1]){
                    dp[j] = use;
                }else{
                    dp[j] = Math.min(dp[j - 1], dp[j]) + 1;
                }
                use = stor;
            }
        }
        return dp[n2];
    }

    /**
     * dp-数组优化
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance3(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
        int[] pre = new int[length2 + 1];
        int[] dp = new int[length2 + 1];
        for (int i = 1; i <= length1; i++) {
            char target = word1.charAt(i - 1);
            for (int j = 1; j <= length2; j++) {
                pre[j] = dp[j];
                if (target == word2.charAt(j - 1)){
                    dp[j] = pre[j - 1] + 1;
                }else {
                    dp[j] = Math.max(dp[j - 1], dp[j]);
                }
            }
        }
        return length1 + length2 - (dp[length2] << 1);
    }
}
